﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GetZipPwd
{
    /// <summary>
    /// 根据指定位数,和字符集合,返回所有字符的排列组合.
    /// 如给定字符集abc,长度2,返回aa,ab,ac,ba,bb,bc,ca,cb,cc
    /// 
    /// 使用算法:
    /// 由于预计运算量很大(如15位以上,字符集合包含大小写字母和数字),不能用递归的方式.
    /// 采用类似于数字进位的方式.
    /// 也就是,把字符集合看作数字的组合.然后按照集合大小进位,
    /// 类提供了getCurrent,和getNext两个函数,取当前数字,和下一个数字.下一个数字,相当于+1后返回.
    /// 为了便于理解,假如给定字符集合是0123456789abcdef,这个时候,可以用对16进制数字做+1来理解.
    /// 生成3位的组合的时候,相当于生成从000,数到fff,当数到00f的时候,下一个数字进位成010,数到2af的时候,下一个数字是2b0.
    /// 如果数到fff,下一个数字会返回null.同时,缓存的当前数字也会被清空.
    /// </summary>
    class RangeStrMaker
    {
        //密钥备选char列表
        public List<char> chars;
        //返回密钥的位数
        public int StrWidth;

        /// <summary>
        /// 每一位是哪个char
        /// </summary>
        private char[] strArray;
        /// <summary>
        /// 当前的char是在chars中的哪个位置
        /// </summary>
        private int[] posArray;
        /// <summary>
        /// 最大"数字"在char中的位置,当getNext的时候遇到这个数字,就知道该进位了.
        /// </summary>
        private int maxNumPos;
        

        public void Init() {

            strArray = new char[StrWidth];
            posArray = new int[StrWidth];
            maxNumPos = chars.Count-1;
            for (int i = 0; i < strArray.Length; i++) {
                posArray[i] = 0;
                strArray[i] = chars[posArray[i]];
            }
        }
        public string GetNext()
        {
            int pos2Carry = 0;//哪一位需要进位,第一次设置最低位需要进位.

            while (pos2Carry > -1)//进位
            {
                if (pos2Carry >= StrWidth)//溢出,整个串达到了最大值
                {
                    //把字符串设置为错误值.
                    for (int i = 0; i < StrWidth; i++)
                    {
                        posArray[0] = -1;
                        strArray[0] = '*';
                    }
                    return null;
                }
                if (posArray[pos2Carry] < maxNumPos)
                {
                    posArray[pos2Carry] += 1;
                    strArray[pos2Carry] = chars[posArray[pos2Carry]];
                    pos2Carry = -1;//不需要进位了.
                }
                else
                {
                    posArray[pos2Carry] = 0;
                    strArray[pos2Carry] = chars[posArray[pos2Carry]];
                    pos2Carry++;
                }
            }

            return new string(strArray);
        }

        public string GetCurrent() {
            return new string(strArray);
        }
    }
}
